package string;

/**
 * 给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
 * 请你返回让 s 成为回文串的 最少操作次数 。
 * 「回文串」是正读和反读都相同的字符串。
 * <p>
 * 示例 1：
 * 输入：s = "zzazz"
 * 输出：0
 * 解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
 * <p>
 * 示例 2：
 * 输入：s = "mbadm"
 * 输出：2
 * 解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
 * <p>
 * 示例 3：
 * 输入：s = "leetcode"
 * 输出：5
 * 解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
 *
 * @author Jisheng Huang
 * @version 20250611
 */
public class MinInsertion_1312 {

    public static int minInsertions(String s) {
        /*
        序列DP：最长回文子序列
        这题要求让s成为回文串的 最少插入次数，反过来就是求s原本有的最长回文子序列长度
        然后再插入与非回文字符数相等的字符即可
        1.状态定义:f[i][j]代表考虑s[i,j]最长回文子序列长度
        2.状态转移:要求f[i][j]就要比较s[i]与s[j]的值
            2.1 s[i]==s[j] 两个字母都要了，回文长度+2 f[i][j]=f[i+1][j-1]+2
            2.2 s[i]!=s[j] 两个字母最多只能保留一个，f[i][j]=max(f[i+1][j],f[i][j-1])
        3.初始化:f[i][i]=1，其余为0
        4.遍历顺序:i倒序，j正序 && i<j
        5.返回形式:n-f[0][n-1]
         */
        int n = s.length();
        int[][] f = new int[n][n];

        for (int i = 0; i < n; ++i) {
            f[i][i] = 1;
        }

        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }

        return n - f[0][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(minInsertions("zzazz"));
        System.out.println(minInsertions("mbadm"));
        System.out.println(minInsertions("leetcode"));
        System.out.println(minInsertions("acha"));
        System.out.println(minInsertions("amigo"));
    }
}
